package com.mamingchao.foundation.recursion.forceRecursion;

/**
 * 汉诺塔
 * Created by mamingchao on 2024/8/8.
 */
public class Hannuo {

    static void func(int n){
        if (n > 0){
            recursion(n, "左","右", "中");
        }
    }

    /**
     *
     * @param i
     * @param from
     * @param to
     * @param other
     */
    static void recursion(int i, String from, String to, String other){

        if (i == 1){
            // base case
            System.out.println("移动" + from +"侧["+ i+ "] 位置 从" + from + "到" + to);
            return;
        }

        // 第一步，把 1~i-1位置的，从from 挪到 other
        recursion(i-1, from, other, to);
        // 第二部，把 i位置的 ，从from 挪到 to
        System.out.println("移动" + from +"侧[" + i+ "] 位置 从" + from + "到" + to);
        // 第三步，把 1~i-1 的，从 other 挪回到 from
        recursion(i-1, other, from, to);
    }

    public static void main(String[] args) {
        func(3);
    }
}
